#include <stdlib.h>
#include <stdbool.h>
#include <securec.h>

int **edges;
int *edgeColSize;
int *visited;
int *result;
int resultSize;
bool valid;

void dfs(int u) {
    visited[u] = 1;
    for (int i = 0; i < edgeColSize[u]; ++i) {
        if (visited[edges[u][i]] == 0) {
            dfs(edges[u][i]);
            if (!valid) { // 提前结束
                return;
            }
        } else if (visited[edges[u][i]] == 1) {
            valid = false;
            return;
        }
    }
    visited[u] = 2; // 访问成功
    result[resultSize++] = u;
}

int *findOrder(int numCourses, int **prerequisites, int prerequisitesSize, int *prerequisitesColSize, int *returnSize) {
    valid = true;
    edges = (int **) malloc(sizeof(int *) * numCourses);
    for (int i = 0; i < numCourses; i++) {
        edges[i] = (int *) malloc(-1);
    }
    edgeColSize = (int *) malloc(sizeof(int) * numCourses);
    memset_s(edgeColSize, sizeof(int) * numCourses, 0, sizeof(int) * numCourses);
    visited = (int *) malloc(sizeof(int) * numCourses);
    memset_s(visited, sizeof(int) * numCourses, 0, sizeof(int) * numCourses);
    for (int i = 0; i < prerequisitesSize; ++i) {
        int a = prerequisites[i][1];
        int b = prerequisites[i][0];
        edgeColSize[a]++;
        edges[a] = (int *) realloc(edges[a], sizeof(int) * edgeColSize[a]);
        edges[a][edgeColSize[a] - 1] = b;
    }
    result = (int *) malloc(sizeof(int) * numCourses);
    resultSize = 0;
    for (int i = 0; i < numCourses && valid; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    for (int i = 0; i < numCourses; ++i) {
        free(edges[i]);
    }
    free(edges);
    free(edgeColSize);
    free(visited);
    if (!valid) {
        *returnSize = 0;
    } else {
        *returnSize = numCourses;
    }
    for (int i = 0; i < numCourses / 2; ++i) {
        int t = result[i];
        result[i] = result[numCourses - i - 1];
        result[numCourses - i - 1] = t;
    }
    return result;
}

int main() {
//    int numCourses = 2;
//    int prerequisites[][2] = {{1, 0}, };
//    int prerequisitesSize = 1;
//    int prerequisitesColSize = 0;
//    int *p[1];
//    for (int i = 0; i < 1; ++i) {
//        p[i] = prerequisites[i];
//    }
//    int returnSize = 0;
//     findOrder(numCourses, p, prerequisitesSize, &prerequisitesColSize, &returnSize);
//    // int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize
//    for (int i= 0; i < returnSize; ++i) {
//        printf("   %d  ", result[i]);
//    }

    int numCourses = 4;
    int prerequisites[][2] = {{1, 0},
                              {2, 0},
                              {3, 1},
                              {3, 2}};
    int prerequisitesSize = 4;
    int prerequisitesColSize = 0;
    int *p[4];
    for (int i = 0; i < 4; ++i) {
        p[i] = prerequisites[i];
    }
    int returnSize = 0;
    findOrder(numCourses, p, prerequisitesSize, &prerequisitesColSize, &returnSize);
    // int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize
    for (int i = 0; i < returnSize; ++i) {
        printf("   %d  ", result[i]);
    }
}
